#!/usr/bin/python
# -*- coding: utf-8 -*-

lists=[49,38,65,97,76,13,27,49]


#调整堆
def adjust_heap(lists, i, size):
    leftchild = 2*i+1
    rightchild = 2*i+2
    nodemax = i
    if i < size/2:
        if leftchild < size and lists[leftchild] > lists[nodemax]:
            nodemax = leftchild
        if rightchild<size and lists[rightchild] > lists[nodemax]:
            nodemax = rightchild
        if nodemax!= i:
            lists[i], lists[nodemax]=lists[nodemax], lists[i]
            adjust_heap(lists, nodemax, size)
#创建堆
def build_heap(lists, size):
    for i in range(0, int(size/2))[::-1]:
        adjust_heap(lists, i, size)

#排序
def sort_heap(lists):
    size=len(lists)
    build_heap(lists, size)
    print(lists)
    for i in range(0, size)[::-1]:

        lists[0], lists[i]=lists[i], lists[0]
        #print("middle: %s" %lists)
        adjust_heap(lists, 0, i)
        #print("after: %s " %lists)
    return lists


l=sort_heap(lists)
print(l)